2.1 数组

数组是我们常用的一种数据结构，在大部分编程语言中都原生支持，数组在我们的日常开发工作中也是一种必不可少的数据结构。

本节代码存放目录为 lesson2

概念及原理

什么是数组？

数组是最基础的数据结构之一，它是一个固定大小的连续内存块，用于存储相同类型的数据。

每个元素在数组中的位置可以通过索引来访问，索引从 0 开始。

数组的最大特点是：它可以通过索引在常数时间O(1)内访问任意元素，其大小在创建时是固定的，不能动态扩展。

数组的基本结构

• 元素类型：数组中的所有元素必须是相同的数据类型（如整数、浮点数、字符串等）。

• 长度固定：数组的大小在创建时指定，一旦创建就无法改变长度。

• 索引访问：每个数组元素都有一个唯一的索引，访问元素时可以通过索引值直接获取数据，时间复杂度为 O(1)。

数组的存储方式

数组是一块连续的内存区域。假设每个元素占用相同的内存空间，数组中的第一个元素存储在基地址位置，其后的元素依次存储在紧邻的内存位置上。

因此，访问数组元素时，可以通过基地址 + 索引 × 元素大小 直接定位到目标元素。

下图所示为数组存储示意图：

+------+------+------+------+------+
|  1   |  2   |  3   |  4   |  5   |   <--- 数组存储在连续的内存地址中
+------+------+------+------+------+
  ^      ^      ^      ^      ^
  |      |      |      |      |
arr[0]  arr[1]  arr[2] arr[3] arr[4]

从上图我们可以看出数组就是一串线性的连续存储结构，每个元素紧跟前一个元素，就跟我们排队一样。

数组的优缺点

优点：

• 快速访问：通过索引可以在 O(1) 时间内访问任意元素。

• 内存紧凑：数据存储在连续的内存区域，便于缓存优化。

缺点：

• 固定大小：数组的大小在创建时就需要确定，无法动态扩展或缩小。

• 插入和删除效率低：插入和删除操作可能需要移动多个元素，最坏情况下的时间复杂度为 O(n)。

基于数组的优缺点，我们可以大概总结出数组的应用场景：

• 当需要频繁通过索引访问元素时，数组是非常高效的数据结构。

• 数组适合存储已知数量的、同类型的元素，特别是当数组大小不会动态变化的场景。

Go语言的实现

Go数组的声明与初始化

// 声明长度为 5 的整数数组
var arr1 [5]int

// 通过字面量初始化数组
arr2 := [5]int{1, 2, 3, 4, 5}

// 自动推断数组长度
arr3 := [...]int{10, 20, 30}

在上面的代码中，我们通过多种方式声明并初始化了数组，总之就是长度肯定是固定的，如果想要了解Go语言底层也可以点击这里进一步查看。

我们可以通过下方的示意图了解Go语言在数组声明及初始化时具体是怎么样的：

+-----------------+-----------------+-----------------+
| arr1[0]: 0      | arr1[1]: 0      | arr1[2]: 0      |  <--- 声明后默认值为 0
+-----------------+-----------------+-----------------+
| arr1[3]: 0      | arr1[4]: 0      |
+-----------------+-----------------+

+-----------------+-----------------+-----------------+
| arr2[0]: 1      | arr2[1]: 2      | arr2[2]: 3      |  <--- 初始化时赋值
+-----------------+-----------------+-----------------+
| arr2[3]: 4      | arr2[4]: 5      |
+-----------------+-----------------+

Go语言中数组的操作

访问数组元素：在Go语言中，数组的元素可以通过索引直接访问和修改。

   // 访问数组中的元素
   fmt.Println(arr2[2])  // 输出：3

   // 修改数组中的元素
   arr2[2] = 10
   fmt.Println(arr2[2])  // 输出：10

遍历数组：Go语言中可以使用 for 循环和 range 关键字来遍历数组。

   // 通过索引遍历数组
   for i := 0; i < len(arr2); i++ {
       fmt.Println(arr2[i])
   }

   // 使用 range 遍历数组
   for i, v := range arr2 {
       fmt.Printf("arr[%d] = %d\n", i, v)
   }

复制数组：在Go语言中，数组是值类型，赋值时会复制整个数组。

   arrCopy := arr2
   arrCopy[0] = 100
   fmt.Println(arr2[0])  // 输出：1 （原数组未受影响）

数组与切片的区别

在Go语言中，数组和切片是不同的概念。数组的大小固定，而切片是一种更灵活的数据结构，它的大小可以动态变化。可以把数组看作是切片的基础，切片可以基于数组进行创建。

• 数组：大小固定，定义时确定。

• 切片：大小可变，底层使用数组实现。

切片基于数组的示意图如下所示：

+-----------------+-----------------+-----------------+-----------------+-----------------+
| arr[0]: 1       | arr[1]: 2       | arr[2]: 3       | arr[3]: 4       | arr[4]: 5       |  <--- 数组
+-----------------+-----------------+-----------------+-----------------+-----------------+
      |                |                  |
      v                v                  v
+------------+   +------------+    +------------+
| slice[0]: 1|   | slice[1]: 2|    | slice[2]: 3|  <--- 切片引用数组的部分
+------------+   +------------+    +------------+

总的来说，切片的底层就是基于数组的，我们可以通过点击这里查看到切片的详细解释。

数组的常见操作示例

我们下面以两个示例来演示数组的一些实际使用，帮助我们对数组有一个更深的了解。

示例1：查找数组中的最大元素

func findMax(arr [5]int) int {
    max := arr[0]
    for i := 1; i < len(arr); i++ {
        if arr[i] > max {
            max = arr[i]
        }
    }
    return max
}

示例2：反转数组

func reverseArray(arr [5]int) [5]int {
    for i := 0; i < len(arr)/2; i++ {
        arr[i], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[i]
    }
    return arr
}

总结

数组是最基础且常见的数据结构之一，在Go语言中使用数组需要注意它的固定大小特性。

尽管数组操作高效且直观，但在Go中大多数情况下我们会使用更灵活的切片。

了解数组的基础，有助于理解切片和更复杂的数据结构，在Go语言中很多复合结构的底层都会采用数组形式来构成。